import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param board string字符串一维数组
     * @param word string字符串
     * @return bool布尔型
     */
    private StringBuffer[] stringBuffer;
    private String _word;
    private boolean[][] visited;
    public boolean exist (String[] board, String word) {
        // write code here
        int n = board.length;
        _word = word;
        stringBuffer = new StringBuffer[n + 2];
        visited = new boolean[n + 2][board[0].length() + 2];
        for (int i = 0; i < n + 2; i++) {
            stringBuffer[i] = new StringBuffer();
        }
        for (int i = 0; i < board[0].length() + 2; i++) {
            stringBuffer[0].append(" ");
            stringBuffer[n + 1].append(" ");
            visited[0][i] = true;
            visited[n + 1][i] = true;
        }
        for (int i = 0; i < n; i++) {
            stringBuffer[i + 1].append(" ");
            stringBuffer[i + 1].append(board[i]);
            stringBuffer[i + 1].append(" ");
            visited[i + 1][0] = true;
            visited[i + 1][board[0].length() + 1] = true;
        }
        return findFirst();
    }

    private boolean findFirst() {
        int rowMax = stringBuffer.length - 1;
        for (int i = 1; i < rowMax; i++) {
            int colMax = stringBuffer[0].length() - 1;
            for (int j = 1; j < colMax; j++) {
                if (stringBuffer[i].charAt(j) == _word.charAt(0)) {
                    visited[i][j] = true;
                    boolean flag = findNext(i, j, 1);
                    if (flag) {
                        return true;
                    }
                    visited[i][j] = false;
                }
            }
        }
        return false;
    }
    private boolean findNext(int row, int col, int index) {
        if (index == _word.length()) {
            return true;
        }
        if (!visited[row - 1][col] &&
                stringBuffer[row - 1].charAt(col) == _word.charAt(index)) {
            visited[row - 1][col] = true;
            if (findNext(row - 1, col, index + 1)) {
                return true;
            } else {
                visited[row - 1][col] = false;
            }
        }
        if (!visited[row + 1][col] &&
                stringBuffer[row + 1].charAt(col) == _word.charAt(index)) {
            visited[row + 1][col] = true;
            if (findNext(row + 1, col, index + 1)) {
                return true;
            } else {
                visited[row + 1][col] = false;
            }
        }
        if (!visited[row][col - 1] &&
                stringBuffer[row].charAt(col - 1) == _word.charAt(index)) {
            visited[row][col - 1] = true;
            if (findNext(row, col - 1, index + 1)) {
                return true;
            } else {
                visited[row][col - 1] = false;
            }
        }
        if (!visited[row][col + 1] &&
                stringBuffer[row].charAt(col + 1) == _word.charAt(index)) {
            visited[row][col + 1] = true;
            if (findNext(row, col + 1, index + 1)) {
                return true;
            } else {
                visited[row][col + 1] = false;
            }
        }
        return false;
    }
}